BIT Algo/3. Zajęcia/Zadanie 9. (Sortowanie liczb według liczby cyfr jednokrotnych i wielokrotnych).ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> Cyfra jednokrotna to taka, która występuje w danej liczbie dokładnie jeden raz. Cyfra wielokrotna to taka, która występuje w liczbie więcej niż jeden raz. <br> Mówimy, że liczba naturalna $ A $ jest ładniejsza od liczby naturalnej $ B $, jeżeli w liczbie $ A $ występuje więcej cyfr jednokrotnych niż w liczbie $ B $, a jeżeli cyfr jednokrotnych jest tyle samo, to ładniejsza jest ta liczba, która posiada mniej cyfr wielokrotnych. <br> Na przykład: liczba $ 123 $ jest ładniejsza od $ 455 $, liczba $ 1266 $ jest ładniejsza od $ 114577 $, a liczby $ 2344 $ i $ 67333 $ są jednakowo ładne."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "###### Dana jest tablica $ T $, zawierająca liczby naturalne. Proszę zaimplementować funkcję:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "    pretty_sort(T)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "###### która sortuje elementy tablicy $ T $ od najładniejszych do najmniej ładnych. Użyty algorytm powinien być możliwie jak najszybszy. Proszę w rozwiązaniu umieścić 1-2 zdaniowy opis algorytmu oraz proszę oszacować jego złożoność czasową."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# I Sposób"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Omówienie algorytmu"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Wstępne rozważania"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ponieważ mamy posortować liczby według tego, która z nich jest ładniejsza, konieczne jest najpierw wymyślenie klucza, po którym będzie odbywało się sortowanie. Oczywiście można wykorzystać jakiś z algorytmów sortowania o złożoności $ O(n \\cdot log(n)) $ i użyć funkcji, która by porównywała dwie liczby i zwracała informację, która z nich jest ładniejsza, a na podstawie rezultatu, liczby umieszczane byłyby w odpowiedniej kolejności. Nie jest to jednak najszybsze możliwe rozwiązanie, a o najszybsze chodzi w tym zadaniu. Od razu na myśl przychodzą algorytmy sortowania o złożoności liniowej. Wiemy, że są to liczby naturalne, więc z powodzeniem można skorzystać z takiego algorytmu, tylko który dokładnie wybrać? Bucket Sort odpada, ponieważ nie wiemy nic o rozkładzie liczb. Najlepszy okazuje się Counting Sort, ale musimy odpowiednio przygotować te liczby do sortowania, a algorytm odpowiednio zmodyfikować."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Przygotowanie liczb do sortowania"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Po przeczytaniu polecenia jeszcze raz, możemy zauważyć, że mamy podany dokładny \"przepis\" na to, jak mają być sortowane liczby: <br>\n",
    "- liczba naturalna $ A $ jest ładniejsza od $ B $, jeżeli ma więcej cyfr jednokrotnych, <br>\n",
    "- jeżeli liczby $ A $ i $ B $ mają tyle samo cyfr jednokrotnych, ładniejsza jest ta, która ma mniej cyfr wielokrotnych, <br>\n",
    "- jeżeli liczby cyfr jednokrotnych i wielokrotnych w obu liczbach są równe, liczby są jednakowo ładne. <br>\n",
    "\n",
    "Można wyciągnąć wniosek, że największe znaczenie ma liczba cyfr jednokrotnych, później jest liczba cyfr wielokrotnych. Warto więc podzielić liczby tak, by najpierw były sortowane po mniej znaczącej wartości (niemalejąco, bo im większa, tym liczba brzydsza), a więc po liczbie cyfr wielokrotnych, a następnie po bardziej znaczącej liczbie cyfr jednokrotnych (nierosnąco, bo im większa, tym liczba ładniejsza). Musimy więc napisać funkcję, która zwróci nam obie te wartości, a następnie, aby za każdym razem nie zliczać na nowo tych wartości, zapisać np. w postaci 3-elementowej krotki tę liczbę, jej liczbę cyfr jednokrotnych i liczbę cyfr wielokrotnych."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Ostatni krok"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Po posortowaniu liczb (zgodnie z powyższymi zasadami), musimy przejść liniowo po tablicy z posortowanymi liczbami i podmienić krotki, które reprezentują te liczby, na te liczby."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Oszacowanie złożoności"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- $ O(2 \\cdot (n + 11)) = O(n) $ - złożoność sortowania Counting Sortem ($ 2 $ - bo mamy tyle \"kolumn\", po których sortujemy wartości, $ n $ - bo tyle jest liczb, $ 11 $ - bo maksymalna liczba (różnych) cyfr jednokrotnych/wielokrotnych wynosi 10, ale może być również 0 (tzn. brak cyfr jednokrotnych/wielokrotnych) - korzystamy z Counting Sorta wewnątrz Radix Sorta (tak naprawdę to nasz $ pretty_sort $ to zmodyfikowana wersja Radix Sorta, która wykorzystuje algorytm Counting Sort, więc tworzymy tablicę o rozmiarze równym $ 11 $), <br>\n",
    "- $ O(n \\cdot (d + 10)) = O(n \\cdot d) $ - złożoność zliczania cyfr jednokrotnych i wielokrotnych ($ n $ - bo mamy tyle liczb, $ d $ - oznacza liczbę cyfr największej z liczb, $ 10 $ - bo w 10-elementowej tablicy będziemy zliczać cyfry tej liczby) <br>\n",
    "- I kilka razy $ O(n) $ na przepisywanie wartości i zamianę z powrotem krotek na liczby. <br>\n",
    "\n",
    "RAZEM: $ O(n \\cdot d) $"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Implementacja algorytmu"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "def pretty_sort(arr):\n",
    "    # If an array has no more than one element, do not sort\n",
    "    if len(arr) < 2: return\n",
    "    # Map numbers array to an array of prettiness tuples\n",
    "    for i in range(len(arr)):\n",
    "        arr[i] = prettify(arr[i])\n",
    "    # Sort numbers by their prettiness (by a number of multiple\n",
    "    # digits first and then by a number of single digits)\n",
    "    counting_sort(arr, lambda tup: tup[2], rewrite_left_to_right)\n",
    "    counting_sort(arr, lambda tup: tup[1], rewrite_right_to_left)\n",
    "    # Restore the original numbers and place them in an array\n",
    "    # on appropriate positions\n",
    "    for i in range(len(arr)):\n",
    "        arr[i] = arr[i][0]\n",
    "\n",
    "        \n",
    "def rewrite_left_to_right(temp, arr):\n",
    "    for i in range(len(temp)):\n",
    "        arr[i] = temp[i]\n",
    "        \n",
    "        \n",
    "def rewrite_right_to_left(temp, arr):\n",
    "    for i in range(len(temp)):\n",
    "        arr[i] = temp[len(temp)-i-1]\n",
    "        \n",
    "    \n",
    "def prettify(num) -> ('num', 'single digits count', 'multiple digits count'):\n",
    "    counts = [0] * 10\n",
    "    num_cp = num\n",
    "    while num:\n",
    "        num, digit = divmod(num, 10)\n",
    "        counts[digit] += 1\n",
    "    # Count a number of singla and multiple digits\n",
    "    single_count = multiple_count = 0\n",
    "    for count in counts:\n",
    "        if count > 1:\n",
    "            multiple_count += 1\n",
    "        elif count == 1:\n",
    "            single_count += 1\n",
    "    # Return a result tuple\n",
    "    return num_cp, single_count, multiple_count\n",
    "    \n",
    "    \n",
    "def counting_sort(arr, key, rewrite_values):\n",
    "    # Allocate memory for required temporary arrays\n",
    "    counts = [0] * 11\n",
    "    temp = [None] * len(arr)\n",
    "    # Count values repetitions\n",
    "    for val in arr:\n",
    "        counts[key(val)] += 1\n",
    "    # Modify the counts array to indicate how many values \n",
    "    # are not greater than the current one\n",
    "    for i in range(1, len(counts)):\n",
    "        counts[i] += counts[i-1]\n",
    "    # Rewrite values to the temp sorted array\n",
    "    for i in range(len(arr)-1, -1, -1):\n",
    "        idx = key(arr[i])\n",
    "        counts[idx] -= 1\n",
    "        temp[counts[idx]] = arr[i]\n",
    "    # Rewrite sorted values to the initial array\n",
    "    rewrite_values(temp, arr)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "###### Kilka testów"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Input arr:\n",
      "[794772, 933488, 441001, 42450, 271493, 536110, 509532, 424604, 962838, 821872, 870163, 318046]\n",
      "\n",
      "Result:\n",
      "[318046, 870163, 271493, 962838, 509532, 536110, 424604, 42450, 794772, 821872, 933488, 441001]\n",
      "\n",
      "(318046, 6, 0)\n",
      "(870163, 6, 0)\n",
      "(271493, 6, 0)\n",
      "(962838, 4, 1)\n",
      "(509532, 4, 1)\n",
      "(536110, 4, 1)\n",
      "(424604, 3, 1)\n",
      "(42450, 3, 1)\n",
      "(794772, 3, 1)\n",
      "(821872, 2, 2)\n",
      "(933488, 2, 2)\n",
      "(441001, 0, 3)\n"
     ]
    }
   ],
   "source": [
    "import random\n",
    "\n",
    "random.seed(0)\n",
    "\n",
    "arr = [random.randint(0, 1_000_000) for _ in range(random.randint(0, 25))]\n",
    "print('Input arr:', arr, sep='\\n', end='\\n\\n')\n",
    "pretty_sort(arr)\n",
    "print('Result:', arr, sep='\\n', end='\\n\\n')\n",
    "\n",
    "for num in arr:\n",
    "    print(prettify(num))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# II Sposób (lepszy)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Omówienie algorytmu"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Możemy wykorzystać taki trick, że każdą z liczb przekształcimy na inną liczbę, która będzie zależała od liczby cyfr jednokrotnych i liczby cyfr wielokrotnych, zgodnie z poniższym wzorem:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "    pretty_num = (10 - single_count) * 100 + multiple_count"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "gdzie $ pretty\\_num $ będzie liczbą, po której będziemy sortować liczby z tablicy wejściowej, $ single\\_count $ to liczba pojedynczych cyfr, a $ multiple\\_count $ to liczba cyfr wielokrotnych. Wzór ma taką postać, ponieważ obie wartości ($ single\\_count $ oraz $ multiple\\_count $) są z przedziału $ \\{0, 1, 2, ..., 9, 10\\} $, więc aby jedna nie nachodziła na drugą, musimy pierwszą z nich (bardziej znaczącą) umieścić z przodu liczby wynikowej, a więc przesunąć o $ 2 $ miejsca w lewo, robiąc miejsce dla pozostałej, maksymalnie $ 2 $-cyfrowej liczby. Nie używamy po prostu $ single\\_count $, ponieważ chcemy, że by najpierw były liczby najładniejsze, czyli te, dla których $ single\\_count $ ma wartość największą. Ponieważ Counting Sort z reguły sotuje liczby w kolejności niemalejącej, musimy spowodować, aby liczby najładniejsze, zmapowane do $ pretty\\_num $ miały najmniejszą wartość. Oczywiście do liczby dodajemy $ multiple\\_count $ już normalnie, bo im większa wartość, tym liczba jest brzydsza, a więc będzie dalej."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Implementacja algorytmu"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def pretty_sort(arr):\n",
    "    # If an array has no more than one element, do not sort\n",
    "    if len(arr) < 2: return\n",
    "    # Map numbers array to an array of prettiness tuples\n",
    "    for i in range(len(arr)):\n",
    "        arr[i] = prettify(arr[i])\n",
    "    # Sort numbers by their prettiness\n",
    "    counting_sort(arr, lambda tup: tup[1])\n",
    "    # Restore the original numbers and place them in an array\n",
    "    # on appropriate positions\n",
    "    for i in range(len(arr)):\n",
    "        arr[i] = arr[i][0]\n",
    "\n",
    "    \n",
    "def prettify(num) -> ('num', 'pretty_num'):\n",
    "    counts = [0] * 10\n",
    "    num_cp = num\n",
    "    while num:\n",
    "        num, digit = divmod(num, 10)\n",
    "        counts[digit] += 1\n",
    "    # Count a number of singla and multiple digits\n",
    "    single_count = multiple_count = 0\n",
    "    for count in counts:\n",
    "        if count > 1:\n",
    "            multiple_count += 1\n",
    "        elif count == 1:\n",
    "            single_count += 1\n",
    "    # Return a result tuple\n",
    "    return num_cp, (10 - single_count) * 100 + multiple_count\n",
    "    \n",
    "    \n",
    "def counting_sort(arr, key):\n",
    "    # Allocate memory for required temporary arrays\n",
    "    counts = [0] * 1011  # Max possible value is 10 * 100 + 10 = 1010 and min is 0\n",
    "    temp = [None] * len(arr)\n",
    "    # Count values repetitions\n",
    "    for val in arr:\n",
    "        counts[key(val)] += 1\n",
    "    # Modify the counts array to indicate how many values are not greater than the current one\n",
    "    for i in range(1, len(counts)):\n",
    "        counts[i] += counts[i-1]\n",
    "    # Rewrite values to the temp sorted array\n",
    "    for i in range(len(arr)-1, -1, -1):\n",
    "        idx = key(arr[i])\n",
    "        counts[idx] -= 1\n",
    "        temp[counts[idx]] = arr[i]\n",
    "    # Rewrite sorted values to the initial array\n",
    "    for i in range(len(temp)):\n",
    "        arr[i] = temp[i]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "###### Kilka testów"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Input arr:\n",
      "[794772, 933488, 441001, 42450, 271493, 536110, 509532, 424604, 962838, 821872, 870163, 318046]\n",
      "\n",
      "Result:\n",
      "[271493, 870163, 318046, 536110, 509532, 962838, 794772, 42450, 424604, 933488, 821872, 441001]\n",
      "\n",
      "(271493, 400)\n",
      "(870163, 400)\n",
      "(318046, 400)\n",
      "(536110, 601)\n",
      "(509532, 601)\n",
      "(962838, 601)\n",
      "(794772, 701)\n",
      "(42450, 701)\n",
      "(424604, 701)\n",
      "(933488, 802)\n",
      "(821872, 802)\n",
      "(441001, 1003)\n"
     ]
    }
   ],
   "source": [
    "import random\n",
    "\n",
    "random.seed(0)\n",
    "\n",
    "arr = [random.randint(0, 1_000_000) for _ in range(random.randint(0, 25))]\n",
    "print('Input arr:', arr, sep='\\n', end='\\n\\n')\n",
    "pretty_sort(arr)\n",
    "print('Result:', arr, sep='\\n', end='\\n\\n')\n",
    "\n",
    "for num in arr:\n",
    "    print(prettify(num))"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.10.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}